//
// Created by LiuYou on 2021/5/25.
//

#include <cstdlib>
#include <set>
#include <string>
#include <iostream>
#include <unordered_map>
#include <algorithm>

#define DEBUG

/**
 * @brief 集合覆盖问题
 */
int main() {
    // 8个
    // 传入一个数组, 它被转换为集合。
    // 要覆盖8个州
//    std::set<std::string> statesNeeded({"mt", "wa", "or", "id", "nv", "ut", "ca", "az"});
    // 北京、上海、天津、广州、深圳、成都、杭州、大连
    std::set<std::string> statesNeeded({"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"});

#ifdef DEBUG
    std::cout << "statesNeeded: " << std::endl;
    for (const auto& item : statesNeeded) {
        std::cout << item << std::endl;
    }
    std::cout << std::endl;
#endif

    // 广播台
    // 可供选择的广播台清单, 使用散列表来存储。
    std::__umap_hashtable<std::string, std::set<std::string>> stations{};
/*    stations["kone-1"] = std::set<std::string>({"id", "nv", "ut"});
    stations["ktwo-2"] = std::set<std::string>({"wa", "id", "mt"});
    stations["kthree-3"] = std::set<std::string>({"or", "nv", "ca"});
    stations["kfour-4"] = std::set<std::string>({"nv", "ut"});
    stations["kfive-5"] = std::set<std::string>({"ca", "az"});*/

/*    stations["-1"] = std::set<std::string>({"id", "nv", "ut"});
    stations["-2"] = std::set<std::string>({"wa", "id", "mt"});
    stations["-3"] = std::set<std::string>({"or", "nv", "ca"});
    stations["-4"] = std::set<std::string>({"nv", "ut"});
    stations["-5"] = std::set<std::string>({"ca", "az"});*/

    stations["k1"] = std::set<std::string>({"北京", "上海", "天津"});
    stations["k2"] = std::set<std::string>({"北京", "广州", "深圳"});
    stations["k3"] = std::set<std::string>({"上海", "成都", "杭州"});
    stations["k4"] = std::set<std::string>({"上海", "天津"});
    stations["k5"] = std::set<std::string>({"杭州", "大连"});


    // 最终选择的广播台
    // 使用一个集合来存储最终选择的广播台。
    using SetString = std::set<std::string>;
    SetString finalStations;


#ifdef DEBUG
    // TODO 注意: 通过调试阶段对 stations的观察发现
    //  C++ 的散列表 std::__umap_hashtable对键值对中的值会进行排序(如果值有顺序的话)！！！！
    //  而且另外一个重点: std::__umap_hashtable不会对键值进行排序。就是之后顺序遍历散列表的时候, 散列表的输出顺序与你插入键值对时的顺序是不同的！！！！这一点非常重要！！！！
    std::cout << "stations: " << std::endl;
    for (const auto& item : stations) {
        std::cout << item.first << " ";
        for (const auto& elem : item.second) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
#endif

    while (!statesNeeded.empty()) {
        // TODO 注意: 这里知道了为什么将while循环中每次循环使用到的对象定义在循环之外！！！！
        //  因为每次对象的创建和销毁都需要时间消耗！！！！
        //  这里非常重要！！！！！！！！！！！！！！！！！！！！！！！
        std::string bestStation{};
        SetString statesCovered{};

        std::cout << "内层for开始" << std::endl;

        // for循环迭代每个广播台, 并确定它时候是最佳的广播台
        for (const auto& item : stations) {
            std::set<std::string> statesForStation = item.second;
            // 计算每一个item, 即广播台覆盖的州与想要覆盖的8个州的交集。
            std::set<std::string> covered{};
            // TODO 注意:
            //  这里一定要使用 inserter 插入迭代器不然会报错！！！！
            std::set_intersection(statesNeeded.begin(), statesNeeded.end(),
                                  statesForStation.begin(), statesForStation.end(),
                                  std::inserter(covered, std::begin(covered)));
/*            std::set_intersection(statesNeeded.begin(), statesNeeded.end(),
                                  statesForStation.begin(), statesForStation.end(),
                                  covered);*/


            if (covered.size() > statesCovered.size()) {
                bestStation = item.first;
                statesCovered = covered;
            }
        }
        std::cout << "内层for结束" << std::endl;

//        statesNeeded -= statesCovered;
        std::set<std::string> tmp{};
        // TODO 注意:
        //  这里一定要使用 inserter 插入迭代器不然会报错！！！！
//        std::set_difference(statesNeeded.begin(), statesNeeded.end(),
//                            statesCovered.begin(), statesCovered.end(),
//                            tmp.begin());
        std::set_difference(statesNeeded.begin(), statesNeeded.end(),
                            statesCovered.begin(), statesCovered.end(),
                            std::inserter(tmp, std::begin(tmp)));

//        statesNeeded = tmp;
        // TODO 注意: 这里没有进行上一条注释语句的赋值, 而是先将 statesNeeded清空, 然后将 tmp赋值到 statesNeeded。
        //  经过测试直接执行上面的语句也是可以的, 但是我觉得先 自身.clear() 之后在赋值, 这种写法更加科学和更加正确。
        statesNeeded.clear();
        statesNeeded = tmp;


        finalStations.insert(bestStation);
        std::cout << "======================" << std::endl;
        for (const auto& item : finalStations) {
            std::cout << item << std::endl;
        }
        std::cout << "======================" << std::endl;
    }

    for (const auto& item : finalStations) {
        std::cout << item << std::endl;
    }
    // 结果依然是
//    k2
//    k3
//    k4
//    k5
    // 而 k2 k3 k4 k5 是可以完成任务的。
    // 而 k1 k2 k3 k5 也是可以完成任务的。



    std::exit(0);
}